// https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/description/

// 算法思路总结：
// 1. 动态规划求解珠宝最大价值问题
// 2. 使用滚动数组优化空间复杂度
// 3. 状态转移：dp[j] = max(从上而来, 从左而来) + 当前价值
// 4. 时间复杂度：O(m×n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>

class Solution 
{
public:
    int jewelleryValue(vector<vector<int>>& frame) 
    {
        int m = frame.size(), n = frame[0].size();
        vector<int> dp(n + 1, 0);

        for (int i = 1 ; i <= n ; i++)
            dp[i] = dp[i - 1] + frame[0][i - 1];

        for (int i = 1 ; i < m ; i++)
            for (int j = 1 ; j <= n ; j++)
                dp[j] = max(dp[j], dp[j - 1]) + frame[i][j - 1];
                
        return dp[n];
    }
};

int main()
{
    vector<vector<int>> vv1 = {{1,3,1}, {1,5,1}, {4,2,1}};
    Solution sol;

    cout << sol.jewelleryValue(vv1) << endl;

    return 0;
}